/**
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
 */
//动态规划
var longestPalindrome = function(s) {
  const m = s.length;
  let start = 0;
  let end = 0;
  const dp = Array(m).fill().map(() => Array(m).fill(false));
  // 保证 i～j中间已经计算过
  for(let i=m-1;i>=0;i--) { //从下到上
    for(let j=i;j<m;j++) { //从左到右
      if(s[j]==s[i] && (Math.abs(i-j)<2 || dp[i+1][j-1])) {
        dp[i][j]=true;
        if(j-i>end-start){
          start = i;
          end = j;
        }
      }
    }
  }
  return s.slice(start,end+1);
};
/**
 if(j-i>end-start){
          start = i;
          end = j;
        }
 */
console.log(longestPalindrome("a")) //"a"
console.log(longestPalindrome("babad")) //"bab"
console.log(longestPalindrome("cbbd")) //"bb"